/* *
 * Copyright (c) 2004-2005 Mocha Almond Fudge AI, SIT KMUTT. All Rights Reserved.
 *
 * Redistribution and use in source and binary forms, with or without 
 * modification, are permitted provided that the following conditions are met:
 * 
 *  o Redistributions of source code must retain the above copyright notice, 
 *    this list of conditions and the following disclaimer. 
 *     
 *  o Redistributions in binary form must reproduce the above copyright notice, 
 *    this list of conditions and the following disclaimer in the documentation 
 *    and/or other materials provided with the distribution. 
 *     
 *  o Neither the name of Mocha Almond Fudge AI, SIT KMUTT nor the names of 
 *    its contributors may be used to endorse or promote products derived 
 *    from this software without specific prior written permission. 
 */
package jboard.model.ai.search;

import java.util.Vector;

import jboard.model.BoardPosition;
import jboard.model.HeuristicMovement;
import jboard.model.IBoardConstant;
import jboard.model.Move;
import jboard.model.ai.HeuristicCalculation;
import jboard.util.MoveUtil;
import jboard.util.Utilities;

/**
 * MinimaxTree simulate the minimax algorithm in board game
 * 
 * @author Vashira Ravipanich
 */
public class MinimaxTree implements IBoardConstant {
	private Vector bestPath; //Vector of HeuricTicMovement suggest by MINIMAX
	private int depth;
    private HeuristicCalculation hCalculation;
	private int pileStrategy;
	private MinimaxNode root;	// current BPS of this turn, it will change dynamically each turn
	
	/**
	 * Default constructor
	 */
	public MinimaxTree(int pileStrategy) {
	    this.pileStrategy = pileStrategy;
	    this.depth = 0; // has only root node!
	    this.bestPath = new Vector();
		this.hCalculation = new HeuristicCalculation(pileStrategy);
	}
	
	public void constructTree() {
	    expandLeafAtLevel(this.root, 0);
	}
	
	private void expandLeafAtLevel(MinimaxNode curRoot, int level) {
	    /** Terminate part */
	    if(level >= this.depth) {
	        return;
	    }
	    /** Recursive part */
	    /**
	     * 1. Print BPS and toMove from curRoot
	     * X2. Assign heuristic value to curRoot <ALREADY HAVE>
	     * 3. Get list of children BPS (upon to whose turn?)
	     * 4. Assign heuristic value to child BPS
	     * 5. Create MinimaxNode at next level
	     * 6. expandLeafAt next level to the left most child (created MinimaxNode)
	     */
	    // 0. Preconfigure whose turn?
	    int whichColor = BLACK;
	    if(level%2 == 0) {	// MAX level
	        whichColor = BLACK;
	    } else if(level%2 == 1) { // MIN level
	        whichColor = WHITE;
	    }
	    // 1.
	    final BoardPosition curRootBPS = curRoot.getBoardPosition();
	    
	    //2.
	    /** Set previous BPS to calc*/
		hCalculation.setPreviousBoardPosition(curRootBPS);
		
	    // 3.
	    Vector childrenBPS = MoveUtil.calcPossibleBPS(curRootBPS, whichColor); // change
	    /** Shuffle the vector*/
	    childrenBPS = Utilities.shuffle(childrenBPS); 
	    final int nextLevel = level + 1; // go to next level
	    for(int i = 0; i < childrenBPS.size(); i++) {
	        BoardPosition childBPS = (BoardPosition)childrenBPS.get(i);
	        Move childMove = childBPS.getToMove();
	        hCalculation.setCurrentBoardPosition(childBPS);
	        
	        // 4.
	        int heuristicValue = hCalculation.calculate(whichColor);
	        // 5. 
	        MinimaxNode curChild = new MinimaxNode(childBPS, heuristicValue, nextLevel);
	        // X.
	        curRoot.addChild(curChild);
	        
	        
	        // X+1.
	        // Log using Log4J Warnning comment out!
	        System.out.print(childBPS.toString(level));
	        System.out.println(printBPSLevel(level) + printWhoseTurn(whichColor) + childMove);
	        System.out.println(printBPSLevel(level) + "Heuristic Value : " + heuristicValue);
	        System.out.println();
	        
	        // 6.
	        expandLeafAtLevel(curChild, nextLevel);
	    }
	    if(!MoveUtil.isTokenZero(curRoot.getBoardPosition()))
	    	traverse(curRoot);
	}
	
	private MinimaxNode findMax(MinimaxNode[] node){
		MinimaxNode max = node[0];
		int maxSoFar = max.getValue();
		int maxPos = 0;
		for(int i = 1; i < node.length; i++) {	//the skip 0 cuz we guess it the min 
			int currentValue = node[i].getValue();
			if(currentValue > maxSoFar) {
				maxSoFar = currentValue;
				maxPos = i;
			}
		}
		return node[maxPos];
	}
	
	private MinimaxNode findMin(MinimaxNode[] node) {
		MinimaxNode min = node[0];
		int minSoFar = min.getValue();
		int minPos = 0;
		for(int i = 1; i < node.length; i++) {	//the skip 0 cuz we guess it the min 
			int currentValue = node[i].getValue();
			if(currentValue < minSoFar) {
				minSoFar = currentValue;
				minPos = i;
			}
		}
		return node[minPos];
	}
    /**
     * @return Returns the bestPath.
     */
    public Vector getBestPath() {
        return bestPath;
    }
	
    /**
     * @return Returns the depth.
     */
    public int getDepth() {
        return depth;
    }
	
	/**
	 * Auxilary method to debug the BoardPosition in MinimaxNode
	 * @param level
	 * @return
	 */
	private String printBPSLevel(int level) {
	    StringBuffer result = new StringBuffer();
	    for(int i = 0; i < level; i++) { // start tab in level 1!
	        result.append("\t>>> ");
	    }
	    return new String(result);
	}
	
	private String printWhoseTurn(int color) {
	    String result = null;
	    if(color == BLACK) {
	        result = "AI : ";
	    } else if (color == WHITE) {
	        result = "Human : ";
	    }
	    return result;
	}
    /**
     * @param depth The depth to set.
     */
    public void setDepth(int depth) {
        this.depth = depth;
    }
    /**
     * @param root The root to set.
     */
    public void setRoot(MinimaxNode root) {
        this.root = root;
    }
	
	private void traverse(MinimaxNode currentRoot) {
	    MinimaxNode currentChildren[] = currentRoot.getChildren();
	    if(currentRoot.getState() == MinimaxNode.MIN) {
	        MinimaxNode minNode = findMin(currentChildren);
	        currentRoot.setValue(minNode.getValue()); // set it up!
	        
	    } else if(currentRoot.getState() == MinimaxNode.MAX) {
	        MinimaxNode maxNode = findMax(currentChildren);
	        Move toMoveMax = maxNode.getBoardPosition().getToMove();
	        int hValue = maxNode.getValue();
	        currentRoot.setValue(hValue); // set it up!
	        if(currentRoot.getLevel() == 0) {	// RootNode
	            bestPath.clear();
	            bestPath.addElement(new HeuristicMovement(maxNode.getValue()
	            		, maxNode.getBoardPosition().getToMove())); // Add suggest HeuristicMovement
	        }
	    }
	}
}
